Using 'Union find' pattern for problem solving questions

 About the pattern

The pattern is used to group elements into sets based on specified properties. Each element is unique and the sets are non-overlapping meaning each set has distinct elements. Each set forms a tree data structure, each element has a parent and the root of the tree is called the representative element of that set. The parent of this representative node is the same node (itself). If we pick any element of a set and follow its parent node then we will always reach the representative element of the set (root of the tree representing the disjoint set).

The pattern is implemented using two methods

1. find(node): Find the representative of the set containing the node.
2. union(node1, node2): Merges the set containing node1 and node 2 into one.

Let's say we have an array representing numbers 0 to 5. Before we start applying this pattern each element has itself as the parent.

This means we have 6 different unique sets each containing one element. Now we want to start grouping them into a unique set (typically we will have more than one unique set which we will see with an actual example in some time but for this example consider  we want to create a single set).

1. Do union(0, 1): This will merge nodes 0 and 1 together. Change the representative of 0 to 1.
   
   
   
   
   
2. Similarly do
1. union(1,2)
2. union(2,3)
3. union(4,5): Notice how we merged 4 and 5 instead of 3 and 4. This is done just to give you an idea that an element can merge into any disjoint sets based on the property under consideration.
4. union(3,5)

At the end, we have a tree below:

As you would have imagined by now as you are making this disjoint set the size of the tree can be O(N) in the worst case and so is the time complexity of this pattern.

Optimization: We can optimize this further by maintaining the rank of each element which would denote the number of the child node beneath it. So the rank of the representative node will denote the size of the tree it represents (the number of child nodes it has). We can use this rank to then decide which of the two representative nodes should we use as the parent new representative node while merging the two trees corresponding to the two disjoint sets/trees. Eg., above node 5 at the end of iteration has the rank of 6 (5 nodes under it  + 1 counting itself).

With the above optimization, you will now select a new representative node as the representative node with a higher rank among the two getting merged. So it will be something like below:

As you would have guessed by now the tree is balanced with the above approach and guarantees that the TC for search is reduced to log(N) - length of the tree.

So if I have to find the representative of 4, I will find its parent which is 5, and then recursively find its parent till we reach root which in this case is 1. Once the root is reached (node with itself as a parent) we return that node as it is the representative node. As we traverse the length of the tree the TC is log(N).

Using 'Union find' pattern

Now let's try to use this pattern to solve an actual problem-solving question

Problem statement:

For a given integer, n, and an array, edges, return the number of connected components in a graph containing n nodes. 

The array edges[i] = [x, y] indicates that there’s an edge between x and y in the graph.

Constraint:

• 1<=n<=1000
• 0<=edges.length<=500
• edges[I].length == 2
• 0<=x,y<n
• x!=y
• No repeated edges

Notice how the problem statement says that the elements (vertices of the graph) are unique, and there are no repeated edges. Let's see how we can implement this using the union-find method.

Solution:

class UnionFind:

    def __init__(self, n):
        self.parent = []
        for i in range(n):
            self.parent.append(i)
        self.rank = [1] * n
        self.connected_components = n

    def find(self, v):
        if self.parent[v] != v:
            return self.find(self.parent[v])
        return v
   

    def union(self, x, y):
        p1, p2 = self.find(x), self.find(y)
        if p1 != p2:
          if self.rank[p1] < self.rank[p2]:
            self.parent[p1] = p2
          else:
            self.parent[p2] = p1
          self.connected_components = self.connected_components - 1
		
def count_components(n, edges):
  uf = UnionFind(n)
  for edge in edges:
    v1 = edge[0]
    v2 = edge[1]
    uf.union(v1, v2)  
  return uf.connected_components

If we run the above for the following data sets it gives the correct results:

Example 1:

• Input: 5 , [[0,1],[1,2],[3,4]] 
• Output: 2

Example 2:

• Input: 6 , [[0,1],[3,4],[4,5]]
• Output: 3

Now let's try to understand the solution and implementation of the pattern. The core logic of the union pattern is in the UnionFind class. In the constructor, we have initialized 3 things

1. parent - list that tracks the parent of each element
2. rank - list that tracks the rank of each element
3. connected_component - number of connected component

At the start each node has itself assigned as the parent and the rank of each node is 1. Similarly, since each node is separate at the start number of connected components is equal to the number of nodes.

As we iterate over the edges we pass them to the union method to merge them into the single set - remember the pattern is used to split unique elements into disjoint sets (connect component in this case). As we merge the vertices which are supposed to be part of edges we reduce the connected_component by 1 since two elements forming an edge are merged in a single set (representing connected component). At the end when we have parsed each edge we would have completed having unique disjoint sets representing the number of connected components in edges, so we simply return connected_componenets which we have been using to track it.

Also, notice how we are using rank to ensure that while emerging two disjoint sets we set the parent as the one with a higher rank to ensure the resultant tree is balanced and consequently find() operations take log(N).

Related links

• Union find pattern explained in 5 mins (Youtube)

How to print odd and even numbers in order with two threads

Background

Let us say you have two threads - one thread prints even numbers and other one prints odd numbers. You need to design this in such a way that all the numbers are printed in the natural order i.e 1,2,3,4 etc. 

This is more of a synchronization questions rather than a data structure question. You need to understand how threads, synchronization works in order to be able to solve this question. 

How to print odd and even numbers in order with two threads

We can do this two ways -

1. Using Sempahores
2. Using wait and notify

Let us see how we can do this using semaphores -

public static void withSemaphores() throws InterruptedException, ExecutionException {

 Semaphore oddLock = new Semaphore(1);
 Semaphore evenLock = new Semaphore(0);

 Runnable printOdd = () -> {
  for (int i = 1; i < 10; i = i + 2) {
   try {
    oddLock.acquire();
   } catch (Exception e) {
    // TODO Auto-generated catch block
    e.printStackTrace();
   }
   ;
   System.out.println(i);
   evenLock.release();
  }
 };

 Runnable printEven = () -> {
  for (int i = 2; i < 10; i = i + 2) {
   try {
    evenLock.acquire();
   } catch (Exception e) {
    // TODO Auto-generated catch block
    e.printStackTrace();
   }
   System.out.println(i);
   oddLock.release();

  }
 };

 new Thread(printOdd).start();
 new Thread(printEven).start();
}

Before we see how this is actually working you need to understand how semaphores work. They essentially are like permits. You can initialize the semaphore with the initial permits. Let us say semaphore has 2 permits, to begin with. In this case, 2 threads can acquire these permits. The 3rd thread which comes has to wait till one of the 2 permits become available again. Threads that have acquired the permits can release them once they are done. Permits are acquired by acquire() method and released by release() method. To read more about Semaphores you can refer a post I had written earlier -

• Counting Semaphore, CountDownLatch, CyclicBarrier - synchronization methods for concurrency

Also, note I have used Java 8 lambda syntax in the code above. You can read more about lambds -

• Using Lambda Expressions from Java 8

Now with this understanding let's see how the above logic works.

printOdd runnable is responsible for printing odd numbers whereas printEven prints even number. For loop is designed in such a way and it increments by 2 to continue printing respective numbers. We need to start with 1 which is odd, so old thread starts first. Notice we have 2 semaphores - one for odd and one for even. Odd semaphore has 1 permit whereas even semaphore has 0, to begin with. The odd thread can get the permit from an odd semaphore and print the odd value which is 1. Meanwhile, the even thread will get blocked since no permits are available for even semaphore. Only when an odd thread releases even semaphore permit, even thread will go ahead and print 2. That's how each thread locks each other till numbers are printed in sequence.

You can do the same with the wait and notify. You can see both of the above methods on my GitHub repository on data structures - https://github.com/aniket91/DataStructures/blob/master/src/com/osfg/questions/PrintOddEven.java 

Related Links

• Counting Semaphore, CountDownLatch, CyclicBarrier - synchronization methods for concurrency(OSFG)
• Using Lambda Expressions from Java 8(OSFG)
• https://github.com/aniket91/DataStructures

How to check if a Singly Linked List is a Palindrome or not

Background

This is another classic data structure interview question that fall into basic DS problems. You might have seen or known method to find if a String is palindrome or not. You can simply iterate on half of the String and check with reversed other half if it same.

Time Complexity : O(N)
Space Complexity : O(1)

It will be as simple as -

    public static boolean isPalindrome(String str) {
        if(str == null) {
            return false;
        }
        for(int i = 0; i< str.length()/2; i++) {
            if(!(str.charAt(i) == str.charAt(str.length() - i - 1))) {
                return false;
            }
        }
        return true;
    }

Test :

        System.out.println(isPalindrome("ABCDCBA"));
        System.out.println(isPalindrome("ABBA"));
        System.out.println(isPalindrome("ABCD"));

Output:

true
true
false

It can have a variant such that instead of a String you have a Linked List. Now if you have a double linked list it becomes very easy. You start from head and from the tails and keep comparing. Increment the header pointer and decrement the tail pointer in each iteration. Time complexity will be O(N) only.

However the question at hand is of Singly Linked List.

How to check if a Singly Linked List is a Palindrome or not

 

Method 1 : Using a String

 

Iterate over the Linked list and construct a String out of it and then check if that String is a Palindrome.Time complexity O(N) but space complexity is also O(N) since you are now creating a String.

Since interviewer asked you Linked List this is most definitely something he does not want. He could have asked a String palindrome itself if that was the case. But it never hurts to put it out what you are thinking and build upon your answer as you proceed.

 

Method 2 : Using a Stack

 

You can iterate over the Linked List put it's content in stack. Once iteration is over we can iterate over Linked List again and this time with each iteration compare Nodes content with Stacks popped out content. If it does not match it is not a palindrome.

This again has time complexity O(N) and space complexity O(N).

1) Traverse the given list from head to tail and push every visited node to stack.
2) Traverse the list again. For every visited node, pop a node from stack and compare data of popped node with currently visited node.
3) If all nodes matched, then return true, else false.

Code :

    public static boolean isPalindrome(ListNode<String> head) {
        boolean isPanindrome = true;

        Stack<String> stack = new Stack<>();
        ListNode<String> currentNode = head;

        while (currentNode != null) {
            stack.push(currentNode.getValue());
            currentNode = currentNode.getNext();
        }

        currentNode = head;
        while (currentNode != null) {
            if (!currentNode.getValue().equals(stack.pop())) {
                isPanindrome = false;
                break;
            }
            currentNode = currentNode.getNext();
        }
        return isPanindrome;
    }

I have also added it to my Data Structure github repo. Check isPalindrome() method in  https://github.com/aniket91/DataStructures/blob/master/src/com/osfg/questions/LinkedListPalindromeFinder.java 

 

Method 3 : Reversing the 2nd half of the Linked List

 

This is a better version and always one you should aim for. It provides O(N) time complexity and O(1) space complexity -

1) Get the middle of the linked list.
2) Reverse the second half of the linked list.
3) Check if the first half and second half are identical.
4) Construct the original linked list by reversing the second half again and attaching it back to the first half

4th point is optional and depends if you need original List back.

I have added it to my Data Structure github repo. Check isPalindrome2() method in  https://github.com/aniket91/DataStructures/blob/master/src/com/osfg/questions/LinkedListPalindromeFinder.java  

 

Related Links

• Function to check if a singly linked list is palindrome(GFG)
• Data Structure Github repository

Print binary tree in Spiral order

Background

Sometime back we had seen how to traverse a binary tree and print it. We saw -

• Pre-order 
• post-order
• In-order
• level order traversals

Binary Tree Traversal

In this post we will see how to print them in a spiral order.  Consider following tree -

We need to print the tree in following order - 1, 2, 3, 4, 5, 6, 7.

Code

Following recursive approach will help achieve this. Idea is to keep a boolean toggle param to print nodes either from left to right or right to left.

    public static int getHeight(BTreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = getHeight(root.getLeft());
            int rightHeight = getHeight(root.getRight());
            return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
        }
    }


    /**
     * 
     * @param root
     *            if the btrr Worst case time complexity - O(N^2) for skewed
     *            trees No extra space
     */
    public static void printSpiralRecurssive(BTreeNode root) {
        boolean leftToRight = false;
        int height = getHeight(root);
        for (int i = 1; i <= height; i++) {
            printLevelRecurssive(root, i, leftToRight);
            leftToRight = !leftToRight;
        }
    }

    public static void printLevelRecurssive(BTreeNode root, int level, boolean leftToRight) {
        if (level == 1) {
            System.out.println(root.getData());
        } else {
            if (leftToRight) {
                printLevelRecurssive(root.getLeft(), level - 1, leftToRight);
                printLevelRecurssive(root.getRight(), level - 1, leftToRight);
            } else {
                printLevelRecurssive(root.getRight(), level - 1, leftToRight);
                printLevelRecurssive(root.getLeft(), level - 1, leftToRight);
            }
        }
    }

Logic : We first calculate the height of the tree which are basically levels. We then iterate from 1 to height (basically all levels) and print them from left to right or right to left based on the boolean toggle. We toggle this value after each level. For each recursive call we start from root and we go down till we reach the level we want it to be (one next to previously iterated on) based on the height and print nodes.

Complete solution with example is provide under my github repo of Data Structures -

• https://github.com/aniket91/DataStructures/blob/master/src/com/osfg/utils/BTreePrinter.java

In the same link there is a recursive solution as well that takes O(N) extra space to give same result. Iterative solution  -

private static Stack<BTreeNode> leftToRight = new Stack<>();
private static Stack<BTreeNode> rightToLeft = new Stack<>();
public static void printSpiralIterative(BTreeNode root) {

        rightToLeft.push(root);

        while (!rightToLeft.isEmpty() && !leftToRight.isEmpty()) {
            while (!rightToLeft.isEmpty()) {
                BTreeNode node = rightToLeft.pop();
                System.out.println(node.getData());
                if (node.getLeft() != null) {
                    leftToRight.push(node.getLeft());
                }
                if (node.getRight() != null) {
                    leftToRight.push(node.getRight());
                }
            }

            while (!leftToRight.isEmpty()) {
                BTreeNode node = rightToLeft.pop();
                System.out.println(node.getData());
                if (node.getLeft() != null) {
                    rightToLeft.push(node.getLeft());
                }
                if (node.getRight() != null) {
                    rightToLeft.push(node.getRight());
                }
            }
        }

}

Let me know if you have any questions.

Related Links

• Binary Tree Traversal(OSFG)
• Level order traversal in spiral form(GFG)
• https://github.com/aniket91/DataStructures/blob/master/src/com/osfg/utils/BTreePrinter.java

Stariway to Kth floor problem

Question

There are N stairs that you need to take to the kth floor. You can either climb 1 stair at a time or 2 stair at a time. In how many ways you can cover N stairs.

Solution

Solution is simple recursive one. At a particular step 

• If remaining step >=2 then you can either climb 1 step or 2 steps
• Else If remaining step == 1 you dont have a choice, have to climb 1 step
• Else you have reached your destination and have crossed n stairs - increment way

Java solution is as follows - 

    public static int findWays(int stairsClimbed, int totalStairs) {
        
        if(stairsClimbed == totalStairs) {
            return 1;
        }
        
        if((totalStairs - stairsClimbed) >= 2) {
            return findWays(stairsClimbed + 2, totalStairs) + findWays(stairsClimbed + 1, totalStairs);
        }
        else if ((totalStairs - stairsClimbed) == 1) {
            return findWays(stairsClimbed + 1, totalStairs);
        }
        return 0;
    }

You can find detailed Java solution with test cases on git repository - StairwayClimbWaysFinder .

PS : Git link has a bonus solution as well :)

Related Links

• StairwayClimbWaysFinder GIT

Understanding Tries data structure

Standard Tries

The standard Trie for a set of strings S is an ordered tree such that

• Each node but the node is labelled with a character
• The children of a node are alphabetically ordered
• The path from external nodes to the root yield the String of S.

For example see following picture -

How would you represent this in code? Each node will have an array of size 26 (assuming all english characters) where each index of array will store pointer to next node which is essentially next character of the string.

Running time for operations

• A standard trie uses O(W) space.
• Operations find, insert, delete take time O(dm) each where
• w = total size of strings in S,
• m = size of string involved in operation
• d = alphabet size

Compressed Tries

•  Trie with nodes of degree at least 2
• Obtained from standart trie by compressing chains of redundant nodes.

 Applications

Trie has many useful applications like

• Find first prefix in a text (pattern matching)
• or auto complete a text (which is why it can be used in a search engine). The index of a search engine is stored into a compressed trie. Each leaf of trie is associated with a word and has a list of pages (URLs) containing that word called occurrence list. Trie is kept in memory while the occurrence lists are kept in external memory and are ranked by relevance.
• Suffix tree (rooted directed tree whose edges are labelled with non empty substrings of S)
  
  
  
  
  
• The suffix tree for a text X of size N from an alphabet of size d stores all the N suffixes of X is O(N) space. NOTE : There might be a case where a suffix is a prefix of another suffix in which case the suffix will end on an internal mode. To counter this case you can end the alphabet with a special character eg. $. Time complexity to build suffix tree - O(N^2)

Related Links

• Trie Wiki

Lowest Common Ancestor in a Binary Tree.

Background

In one of the previous posts we saw how to find LCA of two nodes in a Binary search tree. In this post we will repeat the same question but now it's just a binary tree not a BST.

 Solution

    public static BTreeNode findLCA(BTreeNode root, int n1, int n2) {

        if (root == null) {
            return null;
        }

        if (root.getData() == n1 || root.getData() == n2) {
            return root;
        }

        BTreeNode leftNode = findLCA(root.getLeft(), n1, n2);
        BTreeNode rightNode = findLCA(root.getRight(), n1, n2);

        if (leftNode != null && rightNode != null) {
            return root;
        }

        return leftNode != null ? leftNode : rightNode;

    } 

I have posted complete solution with test cases on my GIT repo of interview question. You can find the code -

• LCA Finder Git

Logic is as follows -

• If one of the two nodes is the root, then the root itself is the common ancestor.
• If Node a and Node b lie in the left, their Lowest Common Ancestor is in the left.
• If Node a and Node b lie in the right,their Lowest Common Ancestor is in the right.
• Otherwise, root is the Lowest common ancestor.

Related Links

• Lowest Common Ancestor in a Binary Search Tree. (OSFG) 
• LCA Finder Git

Remove repetitive words from a String and return it

Question

Assume you are given a string, write a function that can remove consecutive repeated words in the string and return it. For example,

"Beginning with the first first first first manned Gemini mission in March 1965, commemorative commemorative medallions were prepared for the astronauts at their request. It is unclear who prepared these early medallions only only, only that each individual box containing a medallion bore the word Fliteline."

to

"Beginning with the first manned Gemini mission in March 1965, commemorative medallions were prepared for the astronauts at their request. It is unclear who prepared these early medallions only, only that each individual box containing a medallion bore the word Fliteline."

Make sure you preserving punctuations in the right positions.

Solution

I have written following Java code with various methods that solve variations of above question -

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;

/**
 * 
 * @author athakur
 *
 */
public class RemoveDuplicates {

    public static void main(String args[]) {

        String input = "Beginning with the first first first first manned Gemini mission in March 1965, commemorative commemorative medallions were prepared for the astronauts at their request. It is unclear who prepared these early medallions only only, only that each individual box containing a medallion bore the word Fliteline.";

        System.out.println(removeConsecutiveDuplicates(input));
        System.out.println(removeConsecutiveDuplicatesBetter(input));
        System.out.println(removeAllDuplicates(input));

    }

    public static String removeAllDuplicates(String input) {
        StringBuilder outputBuilder = new StringBuilder();
        Set<String> wordsSet = new HashSet<>();
        StringTokenizer tokenizer = new StringTokenizer(input, " ");
        while (tokenizer.hasMoreTokens()) {
            String word = tokenizer.nextToken();
            if (wordsSet.add(word)) {
                outputBuilder.append(word);
                outputBuilder.append(" ");
            }
        }
        return outputBuilder.toString();
    }

    public static String removeConsecutiveDuplicatesBetter(String input) {

        StringBuilder outputBuilder = new StringBuilder();
        String lastWord = "";
        StringTokenizer tokenizer = new StringTokenizer(input, " ");
        while (tokenizer.hasMoreTokens()) {
            String word = tokenizer.nextToken();
            if (!word.equalsIgnoreCase(lastWord)) {
                outputBuilder.append(word);
                outputBuilder.append(" ");
            }
            lastWord = word;
        }
        return outputBuilder.toString();

    }

    public static String removeConsecutiveDuplicates(String input) {

        if (input == null)
            return null;

        Stack<String> wordsStack = new Stack<>();
        String[] words = input.split(" ");
        for (int i = 0; i < words.length; i++) {
            wordsStack.push(words[i]);
        }

        String lastWord = "";
        String stringWithNoConsecutiveDuplicates = "";

        while (!wordsStack.isEmpty()) {
            String tempPop = wordsStack.pop();
            if (!lastWord.equalsIgnoreCase(tempPop)) {
                stringWithNoConsecutiveDuplicates = tempPop + " "
                        + stringWithNoConsecutiveDuplicates;
            }

            lastWord = tempPop;
        }

        return stringWithNoConsecutiveDuplicates;

    }

}

Note

Couple of points to note. Prefer removeConsecutiveDuplicatesBetter approach as it does not keep all data in memory. So lets say you have a huge file you need to do this operation on you read it line by line and then tokenize it to further process it.

Also note HashSet has add method which returns false if data is already present in the set.

Stack method is more if you want to retain the duplicate consecutive words which are farthest in a line. Irrespective of your approach you need to take care of following -

• Don't keep all the data in the memory (data can be very huge). Using Stack may led to overflow.
• Use minimum space and more efficient lookup. Hashset internally used HashMap to keep the data hence put/get is ~O(1).
• Avoid String concatenation. Use StringBuilder instead.

As you must have already noticed above approaches do not take care of punctuations. You will need separate processing for that.

Related Links

• Difference between StringBuilder and StringBuffer in Java (OSFG)
• IO in Java (Using Scanner and BufferedReader) (OSFG)

Find the row with maximum number of 1s

Background

This is a data structure and an interview question. It goes as follows - 

"Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s."

or to put it another way each row will have either all 0's or all 1's or k 0's and (n-l) 1's given a 2D array of m*n. Also each k 0's are contiguous and same goes with (n-1) 1's. In short they are sorted. This is just to confuse the interviewee and do not give straight hint that we are dealing with sorted things here :)

Example is in screenshot below-

Note : This question is also in GeeksForGeeks site which has solution in C. I am just going to provide solution in Java. So lets get started.

Brute Force

Brute force is the worst complexity approach you can take. It gives solution... just not in efficient way. I believe you should always start with this approach. This helps  you get a better hang of the problem and interviewer will know you can get things done. Efficiency is something you can always work on or get help of colleges or code reviewers (it will comes more fluently with experience). So always start with brute force approach. 

For this brute force approach would be to iterate over all columns in each row and keep a count of maximum no of 1's in each row and index of that row. Finally return it when you are done with the looping. Time complexity for this would be O(m*n) for a 2D array of dimension m*n. So lets see how this would go.

/**
 * @author athakur
 * Brute force approach
 */
public class BruteForce {
    
    public int compute(int[][] array) 
    {
        int maxRowOnesIndex = 0;
        int maxRowOnesCount = 0;
        for(int i=0;i<array.length;i++)
        {
            int localMaxOnesCount = 0;
            for(int j=0; j<array[i].length;j++)
            {
                if(array[i][j] == 1) {
                    localMaxOnesCount++;
                }
            }
            if(localMaxOnesCount > maxRowOnesCount)
            {
                maxRowOnesCount = localMaxOnesCount;
                maxRowOnesIndex = i;
            }
        }
        return maxRowOnesIndex;
    }
}

To use this methods class and test the working execute following code.

 /**
 * @author athakur
 * Starter code for computing row with maximum 1's in a 2D array
 */
public class Compute {
    public static void main(String args[])
    {
        int[][] array = new int[][]{{0,1,1,1},{0,0,1,1},{1,1,1,1},{0,0,0,0}};
        System.out.println(new BruteForce().compute(array));
    }
}

Output : 2

That's the brute force method. As mentioned earlier it's time complexity is O(m*n) which is like the worst complexity. Can we do better than this? Sure we can :)

What is it that we can leverage here? We know that each row in the 2D array is sorted. We can easily to a binary search to find the leftmost 1. Count of 1st will be no of columns minus index of leftmost one. Now guess what the time complexity is for this approach?

It is O(m*logn). We iterate over each row (total of m rows) and then do a binary search on each row with log n complexity.

/**
 * @author athakur
 * Binary Search approach
 */
public class BinarySearch {

    private int first(int[] array, int low, int high)
    {
        if(high >= low)
        {
            int mid = low + (high-low)/2;
            if((mid == 0 || array[mid-1]==0) && (array[mid] == 1))
            {
                return mid;
            }
            else if(array[mid] == 0) {
                return first(array, mid + 1, high);
            }
            else {
                return first(array, low, mid-1);
            }
        }
        return -1;
    }
   
    public int compute(int [][] array)
    {
        int maxRowOnesIndex = 0;
        int maxRowOnesCount = 0;
        
        for(int i=0; i< array.length;i++)
        {
            int onesIndex = first(array[i], 0, array[i].length-1);
            if(onesIndex != -1)
            {
                int localMaxOnesCount = array.length - onesIndex;
                if(localMaxOnesCount > maxRowOnesCount)
                {
                    maxRowOnesCount = localMaxOnesCount;
                    maxRowOnesIndex = i;
                }
            }
        }
        return maxRowOnesIndex;
    }
    
}

And run it with

/**
 * @author athakur
 * Starter code for computing row with maximum 1's in a 2D array
 */
public class Compute {
    public static void main(String args[])
    {
        int[][] array = new int[][]{{0,1,1,1},{0,0,1,1},{1,1,1,1},{0,0,0,0}};
        System.out.println(new BinarySearch().compute(array));
    }
}

Output :2

Note : The above solution can be optimized further. Instead of doing binary search in every row, we first check whether the row has more 1s than max so far. If the row has more 1s, then only count 1s in the row. Also, to count 1s in a row, we don’t do binary search in complete row, we do search in before the index of last max.

So basically lets say 1st row has m 1's we will check for each for the subsequent row i whether array[i][n-m-1] is 1.

Related Links

• Find the row with maximum number of 1s (GFG)

Find the Number Occurring Odd Number of Times

Question : 

You are given an array of integers. All integers in the array appear exactly twice except one integer. Your goal is to find and return that integer. For example if you have an array 1,2,3,4,4,3,2,1,7,9,9 you have to return number 7.

Approach : 

When I first encountered this question in an interview I said we can use a HashMap. Iterate the array and store the integers in the Map with key as the integer itself and value as the count of number of times the integer occurs in the array. Then simply iterate the HashMap and return the key with value equal to one. 

Time Complexity -> O(N)

Space Complexity -> O(N)

But there is a better approach - one that involves no extra space. 

Do bitwise XOR of all the elements. Finally we get the number which has odd occurrences i.e 1 in our case.

Later I found out that it is very common question asked.   The questions is

Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times. Find the number in O(n) time & constant space.(GeeeksForGeeks) 

You can see the simple C solution in above link. Below code is for the original question I encountered. So simply xor all the values and return the result.

Code :

package Arrays;

/**
 * Created by Aniket on 3/26/14.
 */
public class SingleCountElementFinder {

    public static int returnNumber(int[] array){

        int no = array[0];

        for(int i=1;i<array.length;i++){
            no = no ^ array[i];
        }

        return no;

    }


    public static void main(String args[]){

        int[] array = new int[]{1,2,3,4,4,3,2,1,7,9,9};
        System.out.println("Single occurring element : " + SingleCountElementFinder.returnNumber(array));

    }

}

Output : 

Single occurring element : 7

NOTE : If you did not know already XOR operation return true if the inputs are different and false if they are same. So if you XOR a number with itself you will get back 0. And if you XOR any number with 0 you get back that number. So in above question each pair of same numbers when XORed gives 0 and finally when XORed with a single instance of the number gives back that number.

Iterative binary tree traversal

Background

In last post Binary Tree Traversal  we saw recursive method to print the tree. We saw DFS(Depth first search) approach which included pre order, post order and in order traversal and we also saw BFS(Breath first search) approach which includes level order traversal.

In this post we will see an iterative way of implementing the DFS approach. Implementation is very simple and uses stack data structure.

Code :

package Tree;

import java.util.Stack;

/**
 * Created by Aniket on 3/14/14.
 */
public class IterativeTreePrinter {

    public static void printIterativePreOrderTraversal(TreeNode root){

        Stack<TreeNode> stack = new Stack<TreeNode>();

        while(root != null){
            System.out.println("Date : " + root.getData());
            if(root.getRightNode() != null){
                stack.push(root.getRightNode());
            }
            if(root.getLeftNode() != null){
                stack.push(root.getLeftNode());
            }

            if(!stack.isEmpty()){
                root = stack.pop();
            }
            else {
                root = null;
            }
        }
    }


    public static void printIterativeInOrderTraversal(TreeNode root){

        Stack<TreeNode> stack = new Stack<TreeNode>();

        while(!stack.isEmpty() || root != null){
            if(root != null){
                stack.push(root);
                root = root.getLeftNode();
            }
            else {
                root = stack.pop();
                System.out.println("Data : " + root.getData());
                root = root.getRightNode();
            }
        }
    }

    public static void printIterativePostOrder(TreeNode root){

        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode peekNode = null;
        TreeNode lastVisitedNode = null;

        while(!stack.isEmpty() || root != null){

            if(root != null){
                stack.push(root);
                root = root.getLeftNode();
            }
            else {
                peekNode = stack.peek();
                if(peekNode.getRightNode() != null && peekNode.getRightNode() != lastVisitedNode){
                    root = peekNode.getRightNode();
                }
                else {
                    stack.pop();
                    System.out.println("Data : " + peekNode.getData());
                    lastVisitedNode = peekNode;
                }

            }


        }
    }

}

Output : 

Output consumes lot of line as I am printing each data in a single line. So I am skipping it in this case. I have tested and verified the code. Output is same as that of recursive method. You can check the output provided in the post( Binary Tree Traversal  ).

Related Links

• Binary Tree Traversal (OSFG)
• DataStructure git repository   
• Print binary tree in Spiral order (OSFG)

Binary Tree Traversal

Binary Tree Traversal

Binary Tree Traversal

Infix to Postfix and Prefix conversion

Question :

Question is simply to covert a given infix expression to both prefix as well as postfix notation. The postfix part of the question is picked up from the code chef question --> Transform the Expression . I have simply extended it to output prefix part as well.

Code :

package CodeChef;

import java.util.Stack;

/**
 * Created by Aniket on 2/23/14.
 */
public class PostFixConverter {

    public static void main(String args[]){
        String infix = "((a+b)*(z+x))";
        System.out.println("Postfix : " + printPostFix(infix));
        System.out.println("Prefix : " + printPreFix(infix));

    }

    public static String printPostFix(String str){
        Stack stack = new Stack();
        String postfix = "";
        for(int i=0;i<str.length();i++){
            char c = str.charAt(i);
            if(Character.isLetter(c)){
                postfix = postfix + c;
            }
            else if(c == '('){
                continue;
            }
            else if(c == ')'){
                postfix = postfix + ((Character)stack.pop()).toString();
            }
            else{
                stack.push(c);
            }
        }
        return postfix;

    }

    public static String printPreFix(String str){
        Stack stack = new Stack();
        String prefix = "";
        for(int i=str.length()-1;i>=0;i--){
            char c = str.charAt(i);
            if(Character.isLetter(c)){
                prefix = ((Character)c).toString() + prefix;
            }
            else if(c == '('){
                prefix = ((Character)stack.pop()).toString() + prefix;
            }
            else if(c == ')'){
                continue;
            }
            else{
                stack.push(c);
            }
        }
        return prefix;

    }

}

Output :

Postfix : ab+zx+*
Prefix : *+ab+zx

Note :

 Note that the expression provided as input is well bracketed input and hence we are not taking care of ordering. If the question asks for ordering then you need to take care of that as well. For example if infix expression in a+b*c answer(post fix) would be abc*+ and not ab+c*.

Lowest Common Ancestor in a Binary Search Tree.

Question : 

Given values of two nodes in a Binary Search Tree, write a c program to find the Lowest Common Ancestor (LCA). You may assume that both the values exist in the tree. (GeeksForGeeks)

LCA(Lowest Common Ancestor) :

From Wikipedia 

Let T be a rooted tree. The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in T that has both n1 and n2 as descendants (where we allow a node to be a descendant of itself). 

The LCA of n1 and n2 in T is the shared ancestor of n1 and n2 that is located farthest from the root. Computation of lowest common ancestors may be useful, for instance, as part of a procedure for determining the distance between pairs of nodes in a tree: the distance from n1 to n2 can be computed as the distance from the root to n1, plus the distance from the root to n2, minus twice the distance from the root to their lowest common ancestor. (Source Wiki) 

Example :

For example, consider the BST in diagram, LCA of 10 and 14 is 12 and LCA of 8 and 14 is 8.

Solution :

We can solve this problem using BST properties. We can recursively traverse the BST from root. The main idea of the solution is, while traversing from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 or same as one of the n1 or n2, is LCA of n1 and n2 (assuming that n1 < n2). So just recursively traverse the BST in, if node's value is greater than both n1 and n2 then our LCA lies in left side of the node, if it's is smaller than both n1 and n2, then LCA lies on right side. Otherwise root is LCA (assuming that both n1 and n2 are present in BST)

Code : 

package Tree;

/**
 * Created by Aniket on 2/22/14.
 */
public class LCAFinder {

    public static TreeNode findLCA(TreeNode root, int n1,int n2){

        if(root == null){
            return null;
        }

        int data = root.getData();
        if(data > n1 && data > n2){
            return findLCA(root.getLeftNode(),n1, n2);
        }

        if(data < n1 && data < n2){
            return findLCA(root.getRightNode(), n1, n2);
        }
        return root;
    }

    public static void main(String args[]){

        TreeNode root = new TreeNode(20);

        TreeNode l = new TreeNode(8);
        TreeNode r = new TreeNode(22);

        TreeNode ll = new TreeNode(4);
        TreeNode lr = new TreeNode(12);

        TreeNode lrl = new TreeNode(10);
        TreeNode lrr = new TreeNode(14);

        root.setLeftNode(l);
        root.setRightNode(r);

        l.setLeftNode(ll);
        l.setRightNode(lr);

        lr.setLeftNode(lrl);
        lr.setRightNode(lrr);

        System.out.println("LCA : " + findLCA(root,10,14).getData());
    }
}

Output : 

LCA of Node with data 10 and 14 : 12

(You can similarly execute the code for 8 and 14( Answer is 8))

Important Links : 

1. Lowest common ancestor
2. How to find the lowest common ancestor of two nodes in any binary tree?
3.  Lowest Common Ancestor in a Binary Tree. (OSFG)

Search an element in a sorted and pivoted array

Question : 

Link of Question : (GeeksForGeeks)
An element in a sorted array can be found in O(log n) time via binary search. But suppose I rotate the sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time.

Algorithm :

Find the pivot point, divide the array in two sub-arrays and call binary search.
The main idea for finding pivot is – for a sorted (in increasing order) and pivoted array, pivot element is the only only element for which next element to it is smaller than it.
Using above criteria and binary search methodology we can get pivot element in O(logn) time

• Input arr[] = {3, 4, 5, 1, 2}

• Element to Search = 1

1.  Find out pivot point and divide the array in two 

   sub-arrays. (pivot = 2) /*Index of 5*

2. Now call binary search for one of the two sub-arrays.

   • If element is greater than 0th element then search in left array

   • Else Search in right array (1 will go in else as 1 < 0th element(3))

3. If element is found in selected sub-array then return index 
        Else return -1.

Code : 

package Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 5/2/14
 * Time: 12:08 PM
 */
public class RotatedBinarySearcher {

    public int pivotedBinarySearch(int[] array, int no){

        int endIndex = array.length - 1;

        int pivot = findPivot(array,0,endIndex);

        System.out.println("Pivot Index : " + pivot);


        if(pivot == -1){    //Array is just sorted and not rotated
            return binarySearch(array,0,endIndex,no);
        }

        if(array[pivot] == no){
            return pivot;
        }
        else if(array[0] <= no){    //If number is greater than array[0] then it is must be left side of pivot
            return binarySearch(array,0,pivot-1,no);
        }
        else {
            return binarySearch(array,pivot+1,endIndex,no);
        }
    }


    private int findPivot(int [] array, int start, int end){

        if(start > end){
            return -1;
        }

        if(start == end){
            return start;
        }

        int mid = (start + end) / 2;

        if(mid > start && array[mid] < array[mid-1]){
            return mid - 1;
        }
        if(mid < end && array[mid] > array[mid + 1]){
            return mid;
        }

        if(array[mid] <= array[start]){
            return findPivot(array, start, mid-1);
        }
        else {  //array[mid] > array[end]
            return findPivot(array, mid + 1, end);
        }
    }

    private int binarySearch(int[] array, int start, int end, int number){

        if(start > end){
            return -1;
        }

        int mid = (end + start)/2;

        if(array[mid] == number){
            return mid;
        }

        if(number < array[mid]){
            return binarySearch(array, start, mid - 1, number);
        }
        else{
            //number > array[mid]
            return binarySearch(array, mid + 1, end, number);
        }
    }

    public static void main(String args[]){

        int[] array = new int[]{3,4,5,1,2};
        int searchIndex = new RotatedBinarySearcher().pivotedBinarySearch(array,1);
        System.out.println("Number is at index : " + searchIndex);

    }

}

Output : 

Pivot Index : 2
Number is at index : 3

Output maximum repeating integer in an array.

Question : 

Given array of N integers ranging from 0 to N-1. Output maximum repeating integer. Use only O(1) memory.

Idea : 

Idea is to iterate over the array. Computer array[i]%N  which will give back the value in array[i]. Now use this computed value as index and add N to the value at that index. Do this for all elements in the array. Return index of the maximum element in the array. If we have a number say X<N appearing M times(Maximum) then we simply add N value M times to the value present at index X which makes it maximum.

Solution : 

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 3/2/14
 */
public class MaxOccurrencesFinder {

    public static int findMqxOccurrenceNumber(int[] array){

        int numberWithMaxOccurrence = 0;
        int indexOfNumberWithMaxOccurrence = 0;

        int arrayLength = array.length;

        for(int i=0;i<arrayLength;i++){
            array[array[i]%arrayLength]  = array[array[i]%arrayLength] + arrayLength;
        }

        for(int i=0;i<arrayLength;i++){
            if(array[i] > numberWithMaxOccurrence){
                numberWithMaxOccurrence = array[i];
                indexOfNumberWithMaxOccurrence = i;

            }
        }

        return indexOfNumberWithMaxOccurrence;

    }

    public static void main(String args[]){

        //array of length 10
        //permitted values 0-9
        int [] array = new int[]{4,6,1,9,2,4,9,1,4,6};
        System.out.println("Max occurred number : " + MaxOccurrencesFinder.findMqxOccurrenceNumber(array));

    }
}  

Output :

 Max occurred number :4

Print all possible paths from top left to bottom right of a mXn matrix

Question : 

The problem is to print all the possible paths from top left to bottom right of a mXn matrix with the constraints that from each cell you can either move only to right or down.(GeeksForGeeks)

Idea :

The algorithm is a simple recursive algorithm, from each cell first print all paths by going down and then print all paths by going right. Do this recursively for each cell encountered.

Solution :

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 30/1/14
 * Time: 4:39 PM
 * To change this template use File | Settings | File Templates.
 */
public class AllPathsPrinter {

    int [][] array;
    int rowCount;
    int colCount;


    public AllPathsPrinter(int [][]array){

        this.array = array;
        rowCount = array.length;
        colCount = array[0].length;

    }


    public void printAllPaths(int currX, int currY, String path){

        if(currX == rowCount-1){
            for(int j=currY;j<=colCount-1;j++){
                path = path + array[currX][j];
            }
            System.out.println("Path : " + path);
            return;
        }

        if(currY == colCount-1){
            for(int i=currX;i<=rowCount-1;i++){
                path = path + array[i][currY];
            }
            System.out.println("Path : " + path);
            return;
        }
        path = path + array[currX][currY];
        printAllPaths(currX+1, currY, path);
        printAllPaths(currX, currY+1, path);

    }

    public static void main(String args[]){

        int [][] ar = new int[][]{{1, 2, 3}, {4, 5, 6}};
        AllPathsPrinter allPathsPrinter = new AllPathsPrinter(ar);
        allPathsPrinter.printAllPaths(0,0,"");


    }


}

Output :

Path : 1456
Path : 1256
Path : 1236

Convert a given Binary Tree to Doubly Linked List

Question:

Given a Binary Tree (Bt), convert it to a Doubly Linked List(DLL). The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (left most node in BT) must be head node of the DLL.(Taken from GeeksForGeeks)

The idea behind its solution is quite simple and straight.

1.  If left subtree exists, process the left subtree
1. Recursively convert the left subtree to DLL.
2. Then find inorder predecessor of root in left subtree (inorder predecessor is rightmost node in left subtree).
3. Make inorder predecessor as previous of root and root as next of inorder predecessor.
2. If right subtree exists, process the right subtree (Below 3 steps are similar to left subtree).
1. Recursively convert the right subtree to DLL.
2. Then find inorder successor of root in right subtree (inorder successor is leftmost node in right subtree).
3. Make inorder successor as next of root and root as previous of inorder successor.
3. Find the leftmost node and return it (the leftmost node is always head of converted DLL).

 Solution :

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 29/1/14
 * Time: 5:43 PM
 */
public class BTreeToList {

    private static TreeNode btreeToListUtil(TreeNode root){

        if( root == null) {
            return null;
        }

        if(root.getLeftNode() != null){

            TreeNode leftTreeNode = btreeToListUtil(root.getLeftNode());

            while(leftTreeNode.getRightNode() != null){
                leftTreeNode = leftTreeNode.getRightNode();
            }

            leftTreeNode.setRightNode(root);
            root.setLeftNode(leftTreeNode);

        }


        if(root.getRightNode() != null){

            TreeNode rightTreeNode = btreeToListUtil(root.getRightNode());

            while(rightTreeNode.getLeftNode() != null){
                rightTreeNode = rightTreeNode.getLeftNode();
            }

            rightTreeNode.setLeftNode(root);
            root.setRightNode(rightTreeNode);
        }

        return root;

    }

    public static TreeNode btreeToList(TreeNode root){
         TreeNode head = btreeToListUtil(root);
        while(head.getLeftNode() != null){
            head = head.getLeftNode();
        }

        return head;
    }

    public static void printLL(TreeNode root){

        while(root != null){
            System.out.println("Data : " + root.getData());
            root = root.getRightNode();
        }


    }



    public static void main(String args[]){

        TreeNode root = new TreeNode(10);

        TreeNode l = new TreeNode(12);
        TreeNode r = new TreeNode(15);

        TreeNode ll = new TreeNode(25);
        TreeNode lr = new TreeNode(30);

        TreeNode rl = new TreeNode(36);

        root.setLeftNode(l);
        root.setRightNode(r);

        l.setLeftNode(ll);
        l.setRightNode(lr);

        r.setLeftNode(rl);

        printLL(btreeToList(root));

    }

}

Output :

Data : 25
Data : 12
Data : 30
Data : 10
Data : 36
Data : 15